Digital networks now carry voice, facsimile, data and video signals. With the vast amount of data being exchanged, data compression is used in these networks to increase efficiency by transmitting the signals in a compressed form. The cost and time savings are significant and thus highly desirable, which in turn has resulted in a continual demand for improved data compression algorithms.
Data compression is a technique whereby a signal, e.g., computer data, that requires a certain number of bits, is represented or encoded, using fewer bits overall. The ratio between the number of bits required for representing the original signal versus the number of bits required by the encoded signal is generally known as the compression ratio. The complimentary process in which the compressed and encoded signal is expanded and reconstructed to form its original representation is generally known as either decompression, decoding or reconstruction.
Data compression is a technology which has matured over time and includes two types of compression: lossy and lossless. In a lossy compression system, portions of the data that are determined to be less necessary than others are discarded, making exact reconstruction or decompression of the signal impossible. Accordingly, lossy compression is usually employed, for example, in connection with physical signals such as speech, audio, images and video in which exact reconstruction of the original signal is usually not required for perceptive acceptability. Moreover, since these types of signals are generally destined for human perception, such as by the human auditory or visual senses, minor differences between the original and reconstructed signals may either be undetectable by human senses or the slightly degraded signal can be tolerated.
In contrast, lossless compression enables an exact reconstruction of the original signal performed upon decompression and can achieve a perfect recreation of the original signal without the degraded or compromised characteristics of lossy compression techniques. One of the consequences of employing lossless compression, however, is that the compression ratio, or the ability to compress a large number of data bits into a smaller number of data bits, is greatly reduced. Despite this, for certain types of data information, it is imperative that perfect reconstruction of lossless data compression be employed rather than the compromised reconstruction approach characteristic of lossy compression techniques. For example, computer data such as an executable file must be precisely reconstructed, otherwise significant negative effects might occur.
At present, various entropic compression methods and pre-compression transformations exist. The existing lossless compression algorithms are typically categorized according to their approach to extract predictive information and/or repetitive patterns embedded in the signal, e.g., repetition of patterns, and the methods used to efficiently encode the information.
Typically, lossless compression algorithms encode the source information in a more compact and optimized way using global statistics and information.
While utilizing lossless compression techniques for communication purposes, optimized encoding is achieved by using information embedded in the previously transmitted data. However, the encoder and decoder must retain synchronization therebetween regarding the transmitted/received data used to encode/decode that data, in order for such applications to operate successfully.
As may be understood from the above, whenever a lossless compression operation is performed over traffic carried along a communication link (bearer), loss of information, e.g., packet loss in packet-switched networks is a hurdle that should be addressed because even if one bit has been lost, the synchronization between the two ends of the link would be lost and no meaningful decompression of the arriving traffic would be obtained.
An example of a conventional approach to addressing this situation is to adopt an error control mechanism for data transmission such as, for example, Automatic Repeat-reQuest (ARQ), over traffic conveyed along the communication link in order to make the link reliable. In accordance with ARQ, the information used for learning how to carry out the compression is only information known to be available at both ends of the link. One notable disadvantage of this approach, however, is that it dramatically increases the round-trip delay of the communication link, to an extent that it might even be impractical to implement it in certain communication applications.
Another conventional approach is to limit the significance of historical information, thereby limiting the impact of data loss.
Still another technique known in the art is to perform a reset of both ends of the link upon each interval of a predetermined period of time, without taking into account any existing conditions, e.g., that the two ends of the link currently operate properly. A major problem associated with this type of technique is that all information transmitted during the period that extends from after a certain loss of information until the next time a reset is carried out will be lost. The reset operation itself impairs the compression ratio and therefore should not be applied very frequently.
Another conventional approach is to separate the compression/encoding activity from the adaptation/learning activity. By doing so, the adaptation of the encoding scheme is done only on data that the receiving party has confirmed it has received. Unfortunately, this approach suffers from a high degree of complexity.
What is needed, therefore, is an approach that provides a lossless compression technique with a high compression ratio without the complexities and disadvantages of known or conventional approaches.